package com.gitee.wsl.struct.tree.iterator

import com.gitee.wsl.struct.tree.NodeElement
import com.gitee.wsl.struct.tree.TreeElement

/**
 * Tree is iterated by using `Level-order Traversal Algorithm" In level-order traversal we iterating
 * nodes level by level, starting from root, and going deeper and deeper in tree.
 *
 * ```
 * E.g.
 *                    1
 *                  / | \
 *                 /  |   \
 *               2    3     4
 *              / \       / | \
 *             5    6    7  8  9
 *            /   / | \
 *           10  11 12 13
 *
 * Output: 1 2 3 4 5 6 7 8 9 10 11 12 13
 * ```
 */
 class LevelOrderTreeIterator<T,E: TreeElement<T, E>>(root: TreeElement<T, E>) : Iterator<TreeElement<T, E>> {

    private val stack = ArrayDeque<TreeElement<T, E>>()

    init {
        stack.addLast(root)
    }

    override fun hasNext(): Boolean = stack.isNotEmpty()

    override fun next(): TreeElement<T, E> {
        val node = stack.removeFirst()
        if(node is NodeElement)
           node.children?.forEach { stack.addLast(it) }
        return node
    }
}
